from typing import List, Tuple

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        """
        柠檬水找零问题 - 贪心算法解决方案
        
        Args:
            bills: 顾客支付的账单列表
        
        Returns:
            bool: 是否能给所有顾客正确找零
        """
        # 处理空数组
        if not bills:
            return True
        
        # 记录手头的5美元和10美元钞票数量
        count_5 = 0
        count_10 = 0
        
        for bill in bills:
            if bill == 5:
                # 收到5美元，无需找零
                count_5 += 1
            elif bill == 10:
                # 收到10美元，需要找零5美元
                if count_5 >= 1:
                    count_5 -= 1
                    count_10 += 1
                else:
                    return False
            elif bill == 20:
                # 收到20美元，需要找零15美元
                # 贪心策略：优先使用10+5的组合，因为10美元只能用于找零20美元
                if count_10 >= 1 and count_5 >= 1:
                    count_10 -= 1
                    count_5 -= 1
                elif count_5 >= 3:
                    count_5 -= 3
                else:
                    return False
            else:
                # 无效的账单金额
                return False
        
        return True

    def lemonadeChangeWithDetails(self, bills: List[int]) -> Tuple[bool, List[str]]:
        """
        带详细过程的柠檬水找零
        
        Args:
            bills: 顾客支付的账单列表
        
        Returns:
            Tuple[bool, List[str]]: (是否成功, 详细过程)
        """
        if not bills:
            return True, ["没有顾客"]
        
        count_5 = 0
        count_10 = 0
        process = []
        
        for i, bill in enumerate(bills):
            step_info = f"顾客{i+1}支付{bill}美元: "
            
            if bill == 5:
                count_5 += 1
                step_info += "无需找零"
            elif bill == 10:
                if count_5 >= 1:
                    count_5 -= 1
                    count_10 += 1
                    step_info += "找零5美元"
                else:
                    step_info += "无法找零，失败"
                    process.append(step_info)
                    return False, process
            elif bill == 20:
                if count_10 >= 1 and count_5 >= 1:
                    count_10 -= 1
                    count_5 -= 1
                    step_info += "找零10+5美元"
                elif count_5 >= 3:
                    count_5 -= 3
                    step_info += "找零5+5+5美元"
                else:
                    step_info += "无法找零，失败"
                    process.append(step_info)
                    return False, process
            else:
                step_info += f"无效账单金额，失败"
                process.append(step_info)
                return False, process
            
            step_info += f" (当前: 5美元×{count_5}, 10美元×{count_10})"
            process.append(step_info)
        
        return True, process
